#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
struct node{
	int mn[4],tag[4];
	int f[16];
	int l,r;
}t[N<<2];
void build(int x,int l,int r)
{
	t[x].l=l,t[x].r=r;
	for ( int i = 0 ; i < 16 ; i++ )t[x].f[i]=r-l+1;
	if(l==r)return;
	int mid=(l+r)/2;build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
void pu(int x)
{
	for ( int i = 0 ; i < 4 ; i++ )
		t[x].mn[i]=min(t[x<<1].mn[i],t[x<<1|1].mn[i]);
	for ( int i = 0 ; i < 16 ; i++ )
	{
		t[x].f[i]=0;
		int flg1=1,flg2=1;
		for ( int j = 0 ; j < 4 ; j++ )
		{
			if(!((i>>j)&1))continue;
			if(t[x<<1].mn[j]!=t[x].mn[j])flg1=0;
			if(t[x<<1|1].mn[j]!=t[x].mn[j])flg2=0;
		}
		if(flg1)t[x].f[i]+=t[x<<1].f[i];
		if(flg2)t[x].f[i]+=t[x<<1|1].f[i];
	}
}
void pd(int x)
{
	for ( int i = 0 ; i < 4 ; i++ )
	{
		t[x<<1].tag[i]+=t[x].tag[i];
		t[x<<1|1].tag[i]+=t[x].tag[i];
		t[x<<1].mn[i]+=t[x].tag[i];
		t[x<<1|1].mn[i]+=t[x].tag[i];
		t[x].tag[i]=0;
	}
}
void upd(int x,int l,int r,int op,int v)
{
	if(l>r)return;
//	if(x==1)cerr << "upd " << l << " " << r << " " << op << " " << v << endl;
	int lf=t[x].l,rt=t[x].r;
	if(l<=lf&&rt<=r)return t[x].tag[op]+=v,t[x].mn[op]+=v,void();
	if(rt<l||r<lf)return;
	pd(x);upd(x<<1,l,r,op,v),upd(x<<1|1,l,r,op,v);pu(x);
}
int fr[N],a[N],n,flg[N],k,pw[5];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	cin >> n >> k;
	pw[0]=pw[2]=pw[4]=1;
	pw[1]=pw[3]=-1;
	for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
	build(1,1,n);
	for ( int i = 1 ; i <= n ; i++ )
	{
		fr[i]=flg[a[i]];
		flg[a[i]]=i;
	}
	int cnt=0;
	for ( int i = 1 ; i <= n ; i++ )
	{
//		cerr << i << endl;
		upd(1,fr[i]+1,i,0,1);
		upd(1,fr[fr[i]]+1,fr[i],0,-1);
		upd(1,fr[fr[i]]+1,fr[i],1,1);
		upd(1,fr[fr[fr[i]]]+1,fr[fr[i]],1,-1);
		upd(1,fr[fr[fr[i]]]+1,fr[fr[i]],2,1);
		upd(1,fr[fr[fr[fr[i]]]]+1,fr[fr[fr[i]]],2,-1);
		upd(1,fr[fr[fr[fr[i]]]]+1,fr[fr[fr[i]]],3,1);
		upd(1,fr[fr[fr[fr[fr[i]]]]]+1,fr[fr[fr[fr[i]]]],3,-1);
//		cerr << t[1].f[0] << " ";
		for ( int j = 0 ; j < (1ll<<k) ; j++ )
		{
			int flg=1;
			for ( int k = 0 ; k < 4 ; k++ )
				if((j>>k)&1)flg&=t[1].mn[k]==0;
			if(flg)cnt+=pw[__builtin_popcount(j)]*t[1].f[j];
		}
//		for ( int j = 0 ; j < (1ll<<k) ; j++ )cerr <<t[1].f[i] << " ";
//		cerr << endl;
//		cerr << cnt << endl;
	}
//	cerr << endl;
	cout << cnt;
	return 0;
}
/*
 6 3
 6 5 6 4 5 5 
*/

